#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int data;
    struct node *next;
} linklist_t;

linklist_t *create_empty_cyclist_head(void)
{
    linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t));
    h->data = 1; // 循环链表的特点是, 头结点也要参与运算
    h->next = h; // 让头节点的下一个节点指向本省
    return h;
}
int cyclist_insert(linklist_t *h, int value)
{
    linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t));
    p->data = value;
    p->next = h->next; // 接链表第1步
    h->next = p;       //接链表的第2步
    return 0;
}

int cyclist_show(linklist_t *h)
{
    linklist_t *p = h->next; // 让p指向头节点下一个节点, 让头节点作为最后一个节点使用
    printf("单循环链表的内容:");
    while (p != h) // p->next == h 是表示循环一圈
    {
        printf("%d ", p->data); // 输出p指向节点的内容
        p = p->next;            // 移动节点
    }
    // p == h
    if (p == h) // p指向的h了, 作为循环表的最后一个元素
    {
        printf("%d ", p->data); // 输出p指向节点的内容
    }
    printf("\n");
    return 0;
}

// 循环表删除节点时, 要定位到要删除节点的前一个节点
// 如果要删除的节点是头结点 , 必须要更新一个新的头结点
linklist_t * cyclist_delete(linklist_t *h, int value)
{
    linklist_t *p = h; // P 指向h节点
    linklist_t *q;
    while (p->next != h) // 循环一圈少一个
    {
        if (p->next->data == value)
        {
            q = p->next;       // 要删除的节点
            p->next = q->next; // 连接链表
            free(q);
            return h; //  函数要返回, 不返回在最后一个节点时, 会报错,
        }
        p = p->next; // p往后移动
    }
    if (p->next == h) // 表示要删除的是头结点
    {
        q = p->next;       // 要删除的节点
        p->next = q->next; // 连接链表
        free(q);
        return p; //  此时删除的是头结点, 要返回一个新的头 p 
    }
}

int main(int argc, char const *argv[])
{
    linklist_t *H = create_empty_cyclist_head();
    cyclist_insert(H, 2);
    cyclist_insert(H, 3);
    cyclist_insert(H, 4);
    cyclist_insert(H, 5);
    cyclist_insert(H, 6);
    cyclist_insert(H, 7);
    cyclist_insert(H, 8);
    cyclist_insert(H, 9);
    cyclist_insert(H, 10);
    cyclist_show(H);

    H = cyclist_delete(H,10); 
    H = cyclist_delete(H,1); 
    H = cyclist_delete(H,5); 
    cyclist_show(H);
    
    return 0;
}